package dp;

import beans.TreeNode;

/**
 * 337. 打家劫舍 III
 */
public class P337 {
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int[] result = PostOrder(root);
        return Math.max(result[0], result[1]);
    }

    /**
     * @param node
     * @return
     */
    int[] PostOrder(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        } else {
            int[] left = PostOrder(node.left);
            int[] right = PostOrder(node.right);
            //抢当前节点
            int rob = left[1] + right[1] + node.val;
            int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
            return new int[]{rob, notRob};
        }
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.parseToTreeNode("3,4,5,1,3,null,1");
        int result = new P337().rob(root);
        System.out.println(result);
    }
}
